﻿#define _CRT_SECURE_NO_WARNINGS 1
//题目：求二叉树的最大深度
//给定一个二叉树，找出其最大深度。
//二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
//说明 : 叶子节点是指没有子节点的节点。
//示例：
//给定二叉树[3, 9, 20, null, null, 15, 7]，
//
//   3
//  / \
// 9  20
//   / \
// 15   7
//返回它的最大深度 3 。

//struct TreeNode {
//    int val;
//    struct TreeNode* left;
//    struct TreeNode* right;
//    
//};
//int maxDepth(struct TreeNode* root) {
//    if (root == NULL)
//    {
//        return 0;
//    }
//    int leftmax = maxDepth(root->left);
//    int rightmax = maxDepth(root->right);
//    return leftmax > rightmax ? leftmax + 1 : rightmax + 1;
//}


//题目：平衡二叉树
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
//int maxDepth(struct TreeNode* root)
//{
//    if (root == NULL)
//    {
//        return 0;
//    }
//    int leftmax1 = maxDepth(root->left);
//    int rightmax1 = maxDepth(root->right);
//    return leftmax1 > rightmax1 ? leftmax1 + 1 : rightmax1 + 1;
//}
//bool isBalanced(struct TreeNode* root) {
//    if (root == NULL)
//    {
//        return true;
//    }
//    int leftmax = maxDepth(root->left);
//    int rightmax = maxDepth(root->right);
//    return abs(leftmax - rightmax) < 2 && isBalanced(root->left) && isBalanced(root->right);
//}

//牛客网题目：二叉树遍历
//描述
//编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。
//例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。
//输入描述：
//输入包括1行字符串，长度不超过100。
//输出描述：
//可能有多组测试数据，对于每组数据， 输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。 每个输出结果占一行。
//示例1
//输入：
//abc##de#g##f###
//输出：
//c b e g d f a

//
//#include<stdlib.h>
//typedef struct BinaryTree
//{
//    char val;
//    struct BinaryTree* left;
//    struct BinaryTree* right;
//}BTree;
//BTree* CreateBinaryTree(char* str, int* pi)
//{
//    if (str[*pi] == '#')
//    {
//        ++(*pi);
//        return NULL;
//    }
//    BTree* root = (BTree*)malloc(sizeof(BTree));
//    if (root == NULL)
//    {
//        perror("malloc fail:");
//        exit(-1);
//    }
//    root->val = str[*pi];
//    (*pi)++;
//    root->left = CreateBinaryTree(str, pi);
//    root->right = CreateBinaryTree(str, pi);
//    return root;
//}
//void InOrder(struct BinaryTree* root)
//{
//    if (root == NULL)
//    {
//        return;
//    }
//    InOrder(root->left);
//    printf("%c ", root->val);
//    InOrder(root->right);
//}
//int main() {
//    char cp[110];
//    scanf("%s", cp);
//    int i = 0;
//    BTree* root = CreateBinaryTree(cp, &i);
//    InOrder(root);
//    return 0;
//}